package 二零年8月;

/**数组中数字出现的次数
 *
 一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

 思路 ： （1）使用map容器存储，遍历数组，保存不重复的数字即可。（可以统计各数字出现的次数，也可以去除重复的数字），但是要求空间复杂度O（1），八行
        （2）分组位运算 ，使用异或，相同为0，不同为1的规则来解决。
        将数组的所有元素进行异或，最后的结果肯定是那两个单一数字异或后的结果。异或规则是两个相应的bit位相同为0，不同为1。
    根据这个任意找一个为1的数位，根据这个数位为0和1分成两个数组，这样必定把两个结果数分开了，再分别异或就能得到结果。

    核心解释：
    回归异或的本质，1^0 = 1, 1^1 = 0, 0^0 = 1。a^b的结果里，为1的位表明a与b在这一位上不相同。这个不相同很关键，
    不相同就意味着我们在结果里任选一位位1的位置i，所有数可以按照i位的取值（0,1）分成两组，
    那么a与b必然不在同一组里。再对两组分别累计异或。那么两个异或结果就是a、b。
 */
public class S56_1 {
    public int[] singleNumbers(int[] nums) {
        int sum=0;
        for (int i = 0; i <nums.length ; i++) {
            sum^=nums[i]; //与所有元素异或得出两个单一数字异或后的值
        }

        //然后根据 1 分组，将这个值再次异或后得到两个单一数字
        int first=1;
        while ((sum&first)==0){ //通过与运算找到第一个sum中不为0的首位,证明a与b在这一位上不相同
            first=first<<1;
        }
        int a=0,b=0;
        for (int num : nums) {    //根据这一位分组异或即可
            if((num & first)==0){
                a^=num;
            }else {
                b^=num;
            }
        }
        return new int[]{a,b};
    }
}
